package com.leetcode.partition9;

/**
 * @author `RKC`
 * @date 2021/10/28 8:56
 */
public class LC869重新排列得到2的幂 {

    public static boolean reorderedPowerOf2(int n) {
        String s = String.valueOf(n);
        int[] nums = new int[s.length()];
        for (int i = 0; i < s.length(); i++) nums[i] = s.charAt(i) - '0';
        return backtracking(nums, nums.length, 0, new boolean[s.length()]);
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(reorderedPowerOf2(n));
    }

    private static boolean backtracking(int[] nums, int count, int n, boolean[] used) {
        //位运算检查是否是2的幂
        if (count == 0) return (n & (n - 1)) == 0;
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (count == nums.length && nums[i] == 0)) continue;
            used[i] = true;
            if (backtracking(nums, count - 1, n + (int) Math.pow(10, count - 1) * nums[i], used)) return true;
            used[i] = false;
        }
        return false;
    }
}
